Algorithmique ≠ Programmation

• Algorithme rédigé en français (conception)
• Codage dans un langage de programmation (programmation)
• Traduction automatique en langage machine (compilation)
• Exécution (partie utilisateur)

Tentative de définition

Exemples connus : +, −, ×, /

• Variables d'entrée : les deux nombres à composer.
• Coeur de l'algorithme : méthode...
• Variable de sortie : résultat du calcul.

Exemple du crible d'Erathostène

• Variables d'entrée : le nombre N où on s'arrête.
• Coeur de l'algorithme : méthode consistant à barrer les multiples...
• Variable de sortie : liste de nombres premiers ≤ N.

Questionnements du concepteur

• Quel type de données dois-je utiliser ?
• Mon algorithme fait-il ce que je veux qu'il fasse ?
• Mon programme s'arrête-t-il toujours ?
• Mon programme est-il efficace ?

Déclarer ses variables

• Une variable associe identifiant unique à une valeur
• Donner une valeur à une variable s'appelle affecter une variable

On note x ← 5

L'instruction a ← a + 1 incrémente la variable a

Différents types de variables

• Le type entier :    1, 0, -2, etc.
• Le type flottant :    2.5, -1, -3.1415, etc.
• Le type booléen :    vrai et faux.
• Le type chaîne :    "Bonjour", "おはよう", "^[0-9a-z]+$", etc.
• Le type composé des listes :    [1, 3, 4], ["abc", "def" ], etc.

Type entier

Les variables de type entier peuvent être composées à l'aide des opérations arithmétiques classique : +, −, ×, ^, /, %, ...

Algorithme calculant le n-ème nombre de Fermat

Entrée : entier n
Variables : entier s
			
s ← 2^(2^n)+1

Sortie : s
						

Type flottant

Les variables de type flottant peuvent être composées à l'aide des opérations classique : +, −, ×, ^, /, sin(.), cos(.), exp(.), ln(.), |.| ...

Algorithme calculant la moyenne de deux nombres réels

Entrées : flottant x, flottant y
Variables : flottant s
			
s ← (x + y)/2

Sortie : s
						

Type booléen

Les variables de type booléen servent à représenter les valeurs de vérité.
Il n'existe que deux booléens, vrai et faux.

Les booléens peuvent être composés à l'aide des fonctions logiques classiques et, ou et non

Algorithme calculant le résultat d'une fonction NOR à partir de deux booléens

Entrées : bool x, bool y
Variables : flottant s
			
s ← non(x ou y)

Sortie : s
						

Les tests logiques

Les fonctions de test <, >, ≤, ≥, = et ≠ renvoient des valeurs booléennes.

Par exemple :

• L'expression (2 < 10) vaut Vrai
• L'expression (2.4 = 2.41) vaut Faux

Calcul de valeurs d'expressions booléennes :

a ← (3 > 1)
b ← (2  ≠  1)
c ← (Vrai = Faux)
d ← ((4,5 = 4)=Faux)
						

Type chaîne

Les variables de type chaîne servent à représenter les valeurs textuelles.

"4µ�®ĥ#.?ğ☜ÐĶĝFÔضEħƕ&§+仮"

Définitions et Notations

• On note C[i] le i-ème caractère de la chaîne C
• On note "" la chaîne vide.
• longueur(C) est la longueur de C
• La concaténation de C et D se note C+D

C ← "Hello"
a ← C[0]
b ← ""
n ← longueur(C)
D ← C + "World"
						

Type composite Liste

Les listes permettent de regrouper en une variable, des valeurs accessibles par leur indice.

Définitions et Notations

• On note L[i] le i-ème élément de la chaîne C
• On note [] la liste vide.
• longueur(L) est le nombre d'éléments de L

L ← [3,1,4,1,5,9,2,6,5,3]
n ← longueur(L)
a ← L[0]
z ← L[9]
						

Liste de listes

Comment représenter ce damier ?

• chaque ligne est une liste de 4 valeurs
• chaque valeur vaut : 1 si il y a un pion, 0 sinon
• il y a 4 lignes

D ← [ [0,0,0,1],[0,1,0,0],[0,0,1,0],[0,0,1,0] ]
						

• D[0] vaut [0,0,0,1]
• D[0][3] vaut 1

Instructions de test et conditions

Un algorithme doit offrir la possibilité de s'adapter à une situation et de choisir :

Si ... alors ... sinon ...

Tests

si condition alors
  instructions
fin si									

si condition alors
  instructions1
sinon 
  instructions2
fin si

Tests multiples :

si condition1 alors
  instructions1
sinon si condition2 alors
  instructions2
sinon si condition3 alors
  instructions3
sinon 
  instructions0
fin si
									

Exemples

Entrée : a
Variables : s
si a ≤ 2015
  s ← "C'est du passé !"
sinon
  s ← "C'est du futur !"
fin si
Sortie : s					

Entrée : login
Variables : s
si login ="admin" alors
  s ←"Bienvenue Ô Maître"
sinon si login = "guest" alors
  s ← "Bienvenue invité"
sinon
  s ← "Sortez d'ici !"
fin si
Sortie : s
								

Tarifs préférentiels :

Entrée : age
Variables : s
si age <6
	alors s ←"Gratuit"
sinon si age < 12
	alors s ← "Tarif Enfant"
sinon si age < 25
	alors s ← "Carte 12-25"
sinon si age < 60
	alors s ← "Plein Tarif"
sinon s ← "Tarif Sénior"
fin si
Sortie : s
								

Boucles "Pour"

Un algorithme doit offrir la possibilité de répéter une série d'instructions N fois :

Répéter N fois la même chose ...

La boucle "Pour"

Pour i de 1 à N
  instructions
fin Pour									

Variables : entier S, entier i

Pour i de 1 à 100
 S ← S+i
fin pour

Sortie : S
								

Variables : liste L, entier i, 
			entier l, entier N

N=longueur de L
l=L[N-1]
Pour i de 1 à N−1
 L[i] ← L[i-1]
fin pour
L[0]=l

Sortie : L 
								

Boucles "Tant que"

Un algorithme doit offrir la possibilité de répéter une série d'instructions autant de fois que nécessaire :

Tant que ... on continue

La boucle "Tant que"

Tant que conditions
  instructions
fin Pour							

Variables : entier i

i ← 1
Tant que i > 0
 i ← i+1
fin Tant que

Sortie : i
								

Entrée : flottant x
Variables : entier n

Tant que x≥1
 x ← x/2
 n ← n+1
fin Tant que

Sortie n
								

Des algorithmes de tri

Exemple d'algorithme de tri fonctionnant sur une liste de cubes imbricables

Le tri par sélection

• Repérer le plus petit élément
• Le placer en début de liste
• Répéter sur une sous-partie non triée

Exemple sur une liste :

Algorithme décomposé

Entrée : liste L
Variables : entiers n, k, i, réel z

n ← longueur de L
pour i de 1 à n−1
  k=indice_min(L,i)
  echange(i,k)
fin pour
Sortie : L
								

Entrée : liste L
Variables : entiers n, k, j

n ← longueur de L
k ← 0
pour j de 1 à n−1
 si L[j]≤L[k] alors
  k ← j
 fin si
fin pour
Sortie : k
								

Entrée : liste L, entiers i, k
Variables : réel z

z ← L[i]
L[i] ← L[k]
L[k] ← z
								

n ← longueur de L
pour i de 1 à n−1
 k ← i
 pour j de i+1 à n−1
  si L[j]≤L[k] alors
   k ← j
  fin si
 fin pour
 
 z ← L[i]
 L[i] ← L[k]
 L[k] ← z
 
 fin pour
								

Le tri à bulle - sur un exemple

Algorithme décomposé

			
booléen échange_effectué ← vrai
tant que échange_effectué = vrai 
	PERMUTATIONS(L)
fin tant que

								

 échange_effectué ← faux
   pour i de 0 à n−1
      si L[i] > L[i + 1]
         ECHANGER(i,i+1)
      échange_effectué = vrai
  fin si
 fin pour

								

Entrée : liste L
Variables : entiers n, i, 
			booléen échange_effectué

tant que échange_effectué = vrai
 échange_effectué ← faux
   pour i de 0 à n−1
   si L[i] > L[i + 1]
      echanger(i,i+1)
   échange_effectué = vrai
  fin si
 fin pour
fin tant que
Sortie : L
								

Les tris en général

Il existe de nombreux algorithmes de tris

Aucun n'est le plus rapide dans tous les cas